﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace::std;


// PTA
 
//// 6 - 1 顺序表统计小于指定元素值个数
//typedef int ElemType;
//typedef struct
//{
//    ElemType* elem;
//    int length;
//}SqList;
//int GetSmaller(SqList L, ElemType e)
//{
//    int count = 0;
//    for (int i = 0; i < L.length; i++)
//    {
//        if (L.elem[i] < e)
//        {
//            count++;
//        }
//    }
//    return count;
//}

//// 6-2 顺序表统计奇数个数
//typedef int ElemType;
//typedef struct
//{
//    ElemType* elem;
//    int length;
//}SqList;
//int OddNumber(SqList L)
//{
//    int count = 0;
//    for (int i = 0; i < L.length; i++)
//    {
//        if (L.elem[i] % 2 != 0)
//        {
//            count++;
//        }
//    }
//    return count;
//}




// LeetCode

//42. 接雨水

// 方法一：动态规划
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution1
{
public:
    int trap(vector<int>& height)
    {
        int n = height.size();
        if (n == 0)
        {
            return 0;
        }

        // 从左开始得到每个位置两边的最大高度
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++)
        {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        // 从右开始得到每个位置两边的最大高度
        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--)
        {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }

        return ans;
    }
};
// 方法二：单调栈
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution2
{
public:
    int trap(vector<int>& height)
    {
        int n = height.size();
        int ans = 0;
        stack<int> st;
        for (int i = 0; i < n; i++)
        {
            while (!st.empty() && height[i] > height[st.top()])
            {
                int top = st.top();
                st.pop();
                if (st.empty())
                {
                    break;
                }
                int left = st.top();
                int wide = i - left - 1;
                int heigh = min(height[left], height[i]) - height[top];
                ans += wide * heigh;
            }
            st.push(i);
        }
        return ans;
    }
};
// 方法三：双指针
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution3
{
public:
    int trap(vector<int>& height)
    {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right)
        {
            // 使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);

            // height[left]<height[right]，则必有 leftMax<rightMax，
            // 下标 left 处能接的雨水量等于 leftMax−height[left]，
            // 将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left + 1
            if (height[left] < height[right])
            {
                ans += leftMax - height[left];
                left++;
            }
            // height[left]≥height[right]，则必有 leftMax≥rightMax，
            // 下标 right 处能接的雨水量等于 rightMax−height[right]，
            // 将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right - 1
            else
            {
                ans += rightMax - height[right];
                right--;

            }
        }
        return ans;
    }
};